Search results for "adjacency matrix"

Adjacency matrices of random digraphs: singularity and anti-concentration

2017

Let ${\mathcal D}_{n,d}$ be the set of all $d$-regular directed graphs on $n$ vertices. Let $G$ be a graph chosen uniformly at random from ${\mathcal D}_{n,d}$ and $M$ be its adjacency matrix. We show that $M$ is invertible with probability at least $1-C\ln^{3} d/\sqrt{d}$ for $C\leq d\leq cn/\ln^2 n$, where $c, C$ are positive absolute constants. To this end, we establish a few properties of $d$-regular directed graphs. One of them, a Littlewood-Offord type anti-concentration property, is of independent interest. Let $J$ be a subset of vertices of $G$ with $|J|\approx n/d$. Let $\delta_i$ be the indicator of the event that the vertex $i$ is connected to $J$ and define $\delta = (\delta_1, …

The effect of fish life-history structures on the topologies of aquatic food webs

2021

Biological organisms can vastly change their ecological functionality due to changes in body size and diet across their life. Consequently, it has been increasingly recognized that to attain sufficient biological realism, food webs may need to include life-history structures. The objective of the work is to study theoretically whether and how the inclusion of life-history structures affects the food web topology. Topological research was done by applying network theory metrics for three different food web types with two different sizes that were generated by using the niche-model. The dynamical modeling was performed by using an allometric trophic network modeling approach. The different ty…

Brain-like large scale cognitive networks and dynamics

2018

A new approach to the study of the brain and its functions known as Human Connectomics has been recently established. Starting from magnetic resonance images (MRI) of brain scans, it is possible to identify the fibers that link brain areas and to build an adjacency matrix that connects these areas, thus creating the brain connectome. The topology of these networks provides a lot of information about the organizational structure of the brain (both structural and functional). Nevertheless this knowledge is rarely used to investigate the possible emerging brain dynamics linked to cognitive functions. In this work, we implement finite state models on neural networks to display the outcoming bra…

PINCoC: a Co-Clustering based Method to Analyze Protein-Protein Interaction Networks

2007

Anovel technique to search for functionalmodules in a protein-protein interaction network is presented. The network is represented by the adjacency matrix associated with the undirected graph modelling it. The algorithm introduces the concept of quality of a sub-matrix of the adjacency matrix, and applies a greedy search technique for finding local optimal solutions made of dense submatrices containing the maximum number of ones. An initial random solution, constituted by a single protein, is evolved to search for a locally optimal solution by adding/removing connected proteins that best contribute to improve the quality function. Experimental evaluations carried out on Saccaromyces Cerevis…

Protein-protein interaction network querying by a "focus and zoom" approach

2008

We propose an approach to network querying in protein-protein interaction networks based on bipartite graph weighted matching. An algorithm is presented that first “focuses” the potentially relevant portion of the target graph by performing a global alignment of this one with the query graph, and then “zooms” on the actual matching nodes by considering their topological arrangement, hereby obtaining a (possibly) approximated occurrence of the query graph within the target graph. Approximation is related to node insertions, node deletions and edge deletions possibly intervening in the query graph. The technique manages networks of arbitrary topology. Moreover, edge labels are used to represe…

Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection

2012

We introduce a span program that decides st-connectivity, and generalize the span program to develop quantum algorithms for several graph problems. First, we give an algorithm for st-connectivity that uses O(n d^{1/2}) quantum queries to the n x n adjacency matrix to decide if vertices s and t are connected, under the promise that they either are connected by a path of length at most d, or are disconnected. We also show that if T is a path, a star with two subdivided legs, or a subdivision of a claw, its presence as a subgraph in the input graph G can be detected with O(n) quantum queries to the adjacency matrix. Under the promise that G either contains T as a subgraph or does not contain T…

An algorithm to find all paths between two nodes in a graph

1990

New structural parameters of fullerenes for principal component analysis

2003

The Kekule structure count and the permanent of the adjacency matrix of fullerenes are related to structural parameters involving the presence of contiguous pentagons p, q, r, q/p and r/p, where p is the number of edges common to two pentagons, q is the number of vertices common to three pentagons and r is the number of pairs of nonadjacent pentagons adjacent to another common pentagon. The cluster analysis of the structural parameters allows classification these parameters. Principal component analysis (PCA) of the structural parameters and the cluster analyses of the fullerenes permit their classification. PCA clearly distinguishes five classes of fullerenes. The cluster analysis of fulle…

Computing the Kekulé structure count for alternant hydrocarbons

2002

A fast computer algorithm brings computation of the permanents of sparse matrices, specifically, molecular adjacency matrices. Examples and results are presented, along with a discussion of the relationship of the permanent to the Kekule structure count. A simple method is presented for determining the Kekule structure count of alternant hydrocarbons. For these hydrocarbons, the square of the Kekule structure count is equal to the permanent of the adjacency matrix. In addition, for alternant structures the adjacency matrix for N atoms can be written in such a way that only an N/2 × N/2 matrix need be evaluated. The Kekule structure count correlates with topological indices. The inclusion of…

Anti-concentration property for random digraphs and invertibility of their adjacency matrices

2016

Let Dn,dDn,d be the set of all directed d-regular graphs on n vertices. Let G be a graph chosen uniformly at random from Dn,dDn,d and M be its adjacency matrix. We show that M is invertible with probability at least View the MathML source1−Cln3⁡d/d for C≤d≤cn/ln2⁡nC≤d≤cn/ln2⁡n, where c,Cc,C are positive absolute constants. To this end, we establish a few properties of directed d-regular graphs. One of them, a Littlewood–Offord-type anti-concentration property, is of independent interest: let J be a subset of vertices of G with |J|≤cn/d|J|≤cn/d. Let δiδi be the indicator of the event that the vertex i is connected to J and δ=(δ1,δ2,…,δn)∈{0,1}nδ=(δ1,δ2,…,δn)∈{0,1}n. Then δ is not concentrate…